package com.shuo.dsa.niuke;

import com.shuo.dsa.model.TreeNode;
import com.shuo.dsa.test.TreeUtil;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <a href="https://blog.csdn.net/xiezongsheng1990/article/details/79574892">输出根节点到叶子的路径</a>
 */
public class PrintRoot2Leaf {

    public static void main(String[] args) {
        TreeNode node = TreeUtil.createTree(12);
        TreeUtil.bfs(node);
        System.out.println(new PrintRoot2Leaf().getAllPath(node));
    }

    /**
     * 广度
     */
    public List<String> getAllPath(TreeNode root) {
        List<String> ret = new ArrayList<>();
        Queue<String> qStr = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        qStr.offer("");
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            String tempStr = qStr.poll();
            if (node.left == null && node.right == null)
                ret.add(tempStr + "->" + node.value);
            if (node.left != null) {
                queue.offer(node.left);
                qStr.offer(tempStr + "->" + node.value);
            }
            if (node.right != null) {
                queue.offer(node.right);
                qStr.offer(tempStr + "->" + node.value);
            }
        }
        return ret;
    }

    // 递归版本一
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new LinkedList<>();
        if (root == null) return paths;
        if (root.left == null && root.right == null) {
            paths.add(root.value + "");
            return paths;
        }
        for (String path : binaryTreePaths(root.left)) {
            paths.add(root.value + "->" + path);
        }
        for (String path : binaryTreePaths(root.right)) {
            paths.add(root.value + "->" + path);
        }
        return paths;
    }


    // 递归版本二
    public List<String> binaryTreePathsRecur(TreeNode root) {
        List<String> result = new LinkedList<>();
        if(root == null) return result;
        getPath(root, result, root.value + "");
        return result;
    }
    private void getPath(TreeNode root, List<String> result, String str){
        if(root.left == null && root.right == null){
            result.add(str);
            return;
        }
        if(root.left != null)
            getPath(root.left, result, str + "->" + root.left.value);
        if(root.right != null)
            getPath(root.right, result, str + "->" + root.right.value);
    }


}
